#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

'''
文件名称：main.py
创 建 者：yang qiang
创建日期：2020年02月19日
版    本：v1.0.0
描    述：
Copyright (C) 2020 All rights reserved.
'''


class Solution(object):
    def findRightInterval(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[int]
        """

        dic = dict()
        res = [-1 for _ in range(len(intervals))]
        for i in range(len(intervals)):
            dic[intervals[i][0]] = i

        intervals.sort(key=lambda x: x[0])
        for i in range(len(intervals)):
            interval = intervals[i]
            start = i + 1
            end = len(intervals)
            while start < end:
                mid = (end - start)/2 + start
                if intervals[mid][0] == interval[1]:
                    start = mid
                    break
                elif intervals[mid][0] > interval[1]:
                    end = mid
                else:
                    start = mid + 1

            if start < len(intervals):
                res[dic[interval[0]]] = dic[intervals[start][0]]

        return res